package com.lsa.letcode.the22.generateValidParenth;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<String> generateParenthesis(int n) {
    	if (n == 0) {
    		return new ArrayList<String>();
    	}
    	List<String> sols = new ArrayList<String>();
    	char[] s = new char[n * 2];
    	generate(sols, s, 0, 0, 0, n);
    	return sols;
    }
    
    private static void generate(List<String> sols, char[] s, int pos, int leftCount, int rightCount, int n) {
    	if (pos == s.length) {
    		sols.add(new String(s));
    	}
    	else {
    		if (leftCount < n) {
    			s[pos] = '(';
    			generate(sols, s, pos + 1, leftCount + 1, rightCount, n);
    		}
    		
    		if (leftCount > rightCount ) {
    			s[pos] = ')';
    			generate(sols, s, pos + 1, leftCount, rightCount + 1, n);
    		}
    	}
    }
}